Krista Garitano

Math 300

Journal Article

There are many interesting questions that have been posed regarding this issue of one-to-one correspondence. One of these questions is, is it possible for a set to be put into one-to-one correspondence with its own power set? This paper will address the issue of one-to-one correspondence and more importantly how it is related to the concept of power sets.

One-to-one correspondence of power sets consists of two cases. One of the cases is that of the infinite set while the other is of the finite set. Although, in order to get a complete understanding of one-to-one correspondence it is important to examine both cases, this paper only examines the finite case.

In order to completely understand what a power set consists of, one must first understand what we think of as an ordinary set is simply a collection of elements. From this we then define a power set as the set of all subsets of a given set. The next step is to see if it is possible to show a one-to-one correspondence between a set and its power set. In order to show a one-to-one correspondence between any two sets, one must show that every element in the original set corresponds to exactly one element in the other set and vice versa.

Since this paper only deals with the case of finite sets, let us begin by taking any finite set. For example, take the arbitrary finite set of n elements where A={a₁, a₂, a₃…a_n }. Thus, the power set of A, denoted by P(A), according to the definition above is, P(A)={{ }, {a₁}, {a₂}…{2ⁿ}}, where n is the number of variables in the original set. In other words, there are 2ⁿ elements in P(A). It is at this stage that we must add a definition. According to Georg Cantor, if the number of elements of each set is equal in magnitude (size), then the two sets may be put into one-to-one correspondence.

From the example of the two sets above, it may be difficult to see if the two sets are equal in magnitude, thus, let us take a smaller finite set that is easier to analyze. Consider the set of three elements, such that, B={a₁, a₂, a₃}. In this case the power set of the set B would be, P(B)={{ }, {a₁}, {a₂}, (a₃}, {a₁, a₂}, {a₁, a₃}, {a₂, a₃}, {a₁, a₂, a₃}}. From this one can actually count the number of elements in the power set, and that number is eight. Similarly, one can extend this reasoning to sets of various numbers of elements, such as, one, two, five or six. The number of elements in a power set can always be found by the number, 2ⁿ, where n is the number of elements in the original set.

From this simple finite set B, one can actually count the number of elements of B, which is three, as well either calculate, from the above number 2ⁿ, or count the number (eight or 2³ ) of elements in the power set of B, P(B). This tells us that the two sets, B and P(B) are not equal in magnitude, and thus can not be put into one-to-one correspondence with one another.

In order to prove this let us assume the opposite, that two sets that are not equal in magnitude can be put into one-to-one correspondence. Thus, let us take any arbitrary set, for example set A, where A={1}. According to the definition of power set, the power set of set A, denoted by P(A), would be P(A)={{ },{1}}. From this example set A only contains one element while the power set P(A) contains two elements. Thus the two sets are unequal in magnitude. Recall, in order to show these two sets can be put into one-to-one correspondence, we must show every element in the original set A corresponds to exactly one element in the power set P(A). We can correspond the element of set A which is {1} to the null set of P(A) which is { }. However, there is still another element in the power set which is {1} that we must correspond to another element in the set of A in order to make a one-to-one correspondence. However, there are no more elements of A, thus we have nothing to correspond the element {1} to. Therefore the two sets which are unequal in magnitude can not be put into one-to-one correspondence.

The above examples can be extended to any finite set of various elements. Yet the result is always the same, it is impossible for any finite set to be put into one-to-one correspondence with its power set.